package arithmetic.LeetCode;

/**
 * 198. 打家劫舍
 *
 * @author jiangfeng on 2023/12/25
 */
public class Rob {
    public static void main(String[] args) {
//        System.out.println(new Solution().rob(new int[]{2,1,1,2}));
        System.out.println(new Solution2().rob(new int[]{6,6,4,8,4,3,3,10}));
    }

    // 打家劫舍2， 首尾相连
    static class Solution2 {
        public int rob(int[] nums) {
            if(nums.length==1){
                return nums[0];
            }
            if(nums.length==2){
                return Math.max(nums[0],nums[1]);
            }
            int[] dp = new int[nums.length];

            // 去掉最后一个
            dp[1] = nums[0];
            for(int i =1;i<nums.length-1;i++){
                dp[i+1] = Math.max(dp[i-1]+nums[i], dp[i]);
            }

            // 去掉第一个
            int[] dp1 = new int[nums.length];
            dp1[1]=nums[1];
            for(int i =2;i<nums.length;i++){
                dp1[i] = Math.max(dp1[i-2]+nums[i], dp1[i-1]);
            }

            return Math.max(dp[nums.length-1],dp1[nums.length-1]);

        }
    }
    static class Solution {
        // [2,1,1,2] 为啥答案是3呢
        public int rob(int[] nums) {
            if (nums.length == 1) {
                return nums[0];
            }
            if (nums.length == 2) {
                return Math.max(nums[0], nums[1]);
            }
            // dp[i] 表示第i个元素时的最大收益。
            // 递归公式：dp[i] = max{dp[i-2]+a[i],dp[i-1]};
            int[] dp = new int[nums.length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0],nums[1]);
            for (int i = 2; i < nums.length; i++) {
                dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            return dp[nums.length - 1];
        }

        public int rob2(int[] nums) {
            // 动态规划, pb n表示第n个元素的最大值是: 选了n-1的最大值,
            // pb[n] = Max{pb[n-1],bp[n-2]+nums[n]}
            if (nums.length == 1) {
                return nums[0];
            }
            if (nums.length == 2) {
                return Math.max(nums[0], nums[1]);
            }
            int prepre = nums[0];
            int pre = Math.max(nums[0], nums[1]);
            for (int i = 2; i < nums.length; i++) {
                int cur = Math.max(prepre + nums[i], pre);

                prepre = pre;
                pre = cur;
            }
            return pre;
        }


    }
}
